The signals within integrated circuits can be many times divided into two classes: clock signals and data signals, each of which has different roles. Generally, phase timing is unconditional for clock signals, whereas data signals are unknown during the clock's phase. In the typical logic circuit design, the data signals propagate through combinational logic and are received at clock signal controlled logic elements such as latches or flip-flops. These clock-controlled circuit elements function to resynchronize the data signals along a scheme common to the circuit as a whole.
Accepting that data signals require some non-zero time to propagate through the combinational logic circuit, it would be desirable to have all of the clock-controlled circuit elements act in unison to resynchronize the flow of data signals. There is, however, delay in clock paths due to combinational logic and interconnect. Therefore, clock signals require time to propagate throughout the integrated circuit. These effects lead to clock skew, which undermines uniform synchronization.
One job of the circuit designer is to manage clock skew. Failure typically occurs where the data signal races the clock signal to some clock-controlled circuit element. If the data reaches the circuit element before the clock, the previous data signal held at the element is lost, and the present data signal is latched through the element on the wrong phase of the clock. This leads to the improper operation of the circuit.
Tools exist for assisting the designer in locating data races within an integrated circuit design. These tools operate on a description of the integrated circuit, typically termed a netlist, which includes such information as the delay through the various logic elements and on the paths between elements within the circuit design. Basically, the tools trace the paths of data signals through the circuit and compare the worst case, i.e., latest, arrival time of a clock signal into a circuit element with the worst case, i.e., earliest, arrival time for the data. The tool confirms whether or not the clock signal will always beat the data signal, typically by some design margin.
Previously, there have been two general schemes for implementing path tracing through an integrated circuit's logic network: breadth-first and depth-first. The former begins at the root node of the combinational tree and steps down each fan-out path from that node to the first-level nodes; this process is then repeated for the first-level nodes until the entire network is covered. The depth-first approach pushes a data signal on a path through the entire network to a leaf node L1, i.e., a node with no children. From L1, L1's parent node N1 is visited and each of N1's children are visited in turn. For each child, if the node has no children, the algorithm returns to Nl; otherwise it visits the children of that child, and so on. Pruning techniques have been used with breadth-first and depth-first analyses in order to reduce the time necessary to analyze a network by removing less critical paths from the analysis.